package com.leecode.xiehf.page_01;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * https://leetcode-cn.com/problems/generate-parentheses/
 */
public class Solution_0023 {

    public static void main(String[] args) {
        Solution_0023 solution_0023 = new Solution_0023();
        ListNode result = solution_0023.mergeKLists(new ListNode[]{
                new ListNode(1,
                        new ListNode(4,
                                new ListNode(5)))
                , new ListNode(1,
                new ListNode(3,
                        new ListNode(4)))
                , new ListNode(2,
                new ListNode(6))
        });
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    /**
     * 归并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeTwoListsRecursive(lists, 0, lists.length - 1);
    }

    public ListNode mergeTwoListsRecursive(ListNode[] list, int left, int right) {
        if (left == right) {
            return list[left];
        }
        int mid = (left + right) / 2;
        ListNode first = mergeTwoListsRecursive(list, 0, mid);
        ListNode second = mergeTwoListsRecursive(list, mid + 1, right);
        return mergeTwoLists(first, second);
    }

    public ListNode mergeTwoLists(ListNode first, ListNode second) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                cur.next = first;
                first = first.next;
            } else {
                cur.next = second;
                second = second.next;
            }
            cur = cur.next;
        }
        cur.next = first == null ? second : first;
        return head.next;
    }

    /**
     * 从每个链表的顶部获取到最小值，然后把拿走了值的链表往上推，
     * 如果有链表为空就把该链表的位置放到数组最后面，下一轮遍历减少
     * <p>
     * 最小堆
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode head = new ListNode(0, null);
        getNode(lists, lists.length, head);
        return head.next;
    }

    void getNode(ListNode[] lists, int length, ListNode head) {
        if (length == 0) {
            return;
        }
        ListNode node = null;
        int minIndex = -1;
        for (int i = 0; i < length; ) {
            ListNode curNode = lists[i];
            if (curNode == null) {
                if (i < length - 1) {
                    lists[i] = lists[length - 1];
                    lists[length - 1] = null;
                }
                length--;
            } else {
                if (node == null) {
                    minIndex = 0;
                    node = new ListNode(curNode.val);
                } else {
                    if (curNode.val < node.val) {
                        minIndex = i;
                        node.val = curNode.val;
                    }
                }
                i++;
            }
        }
        if (minIndex >= 0) {
            lists[minIndex] = lists[minIndex].next;
        }
        if (node == null) {
            return;
        }
        head.next = node;
        getNode(lists, length, node);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

